#include "stdafx.h"
#include "CellSceneBorderLink.h"
#include "CellScene.h"

namespace GraphCutLib
{
	CellNode        CellNode::getLeftNeighbor()
	{
		return CellNode(x - 1,y);
	}

	CellNode        CellNode::getRightNeighbor()
	{
		return CellNode(x + 1,y);
	}

	CellNode        CellNode::getTopNeighbor()
	{
		return CellNode(x,y + 1);
	}

	CellNode        CellNode::getBottomNeighbor()
	{
		return CellNode(x,y - 1);
	}

	CellNode        CellNode::getLeftTopNeighbor()
	{
		return CellNode(x - 1,y + 1);
	}

	CellNode        CellNode::getLeftBottomNeighbor()
	{
		return CellNode(x - 1,y - 1);
	}

	CellNode        CellNode::getRightTopNeighbor()
	{
		return CellNode(x + 1,y + 1);
	}

	CellNode        CellNode::getRightBottomNeighbor()
	{
		return CellNode(x + 1,y - 1);
	}

	bool    CellNode::isNeighbor(const CellNode& node)
	{
		if(getLeftNeighbor() == node)
			return true;

		if(getRightNeighbor() == node)
			return true;

		if(getTopNeighbor() == node)
			return true;

		if(getBottomNeighbor() == node)
			return true;

		if(getLeftTopNeighbor() == node)
			return true;

		if(getLeftBottomNeighbor() == node)
			return true;

		if(getRightTopNeighbor() == node)
			return true;

		if(getRightBottomNeighbor() == node)
			return true;

		return false;
	}

	CellLinkNode    CellLinkNode::extendLinkNode(CellSceneBorderLink& borderLink)
	{
		if(neighborNodeList.size() != 1)
			return CellLinkNode();

		CellNode        offset = pos - borderLink.getLinkNode(neighborNodeList[0])->pos;

		CellLinkNode linkNode;
		//linkNode.neighborNodeList.push_back(pos);
		linkNode.pos = pos + offset;

		//neighborNodeList.push_back(linkNode.pos);

		return linkNode;
	}

	void    CellSceneBorderLink::generatorNeighborInfo()
	{
		const size_t numOfNode = m_borderNodeList.size();

		for (size_t i = 0; i < numOfNode; ++i)
		{
			CellLinkNode&   linkNode = m_borderNodeList[i];
			linkNode.neighborNodeList.clear();

			for (size_t j = 0; j < numOfNode; ++j)
			{
				if(i == j)
					continue;

				CellLinkNode&   nNode = m_borderNodeList[j];

				if(linkNode.pos.isNeighbor(nNode.pos))
					linkNode.neighborNodeList.push_back(nNode.listIndex);
			}
		}

		if(numOfNode == 0)
		{
			m_linkType = EMPTY_LINK;
			return;
		}

		//Èç¹ûÊÇring link£¬Ã¿¸önode¶¼ÓÐ2¸öneighbor
		//ÓÐ1¸öneighborµÄÊÇ·Çring link
		size_t count = 0;
		for (size_t i = 0; i < numOfNode; ++i)
		{
			CellLinkNode&   linkNode = m_borderNodeList[i];
			if(linkNode.neighborNodeList.size() == 1)
				count++;
		}

		if(count > 0)
			m_linkType = NO_RING_LINK;
		else
			m_linkType = RING_LINK;
	}

	void	CellSceneBorderLink::importOrderBorderNode(std::vector<CellNode>& linkNodeList)
	{
		m_borderNodeList.clear();
		m_orderBorderLinkList.clear();
		m_borderNodeList.reserve(linkNodeList.size());
		m_orderBorderLinkList.reserve(linkNodeList.size());

		OrderBorderNodeLink orderLink;
		m_orderBorderLinkList.push_back(orderLink);
		OrderBorderNodeLink& linkRef = *m_orderBorderLinkList.begin();
		for (size_t i = 0; i < linkNodeList.size(); ++i)
		{
			CellLinkNode linkNode;
			linkNode.listIndex = i;
			linkNode.pos = linkNodeList[i];
			m_borderNodeList.push_back(linkNode);
			linkRef.push_back(i);
		}
	}

	void    CellSceneBorderLink::getIntersectRegionLinkHeadNode(std::vector<int>& linkHeadIndexList)
	{
		/*
		现在是分析刚刚得到intersect部分的边界headnode，情况比较简单，就只用neighbor <= 1就判断
		但是有些有些intersect region不规则情况还是有问题，比如下面的B和C，这样的判断就检测不出
		这个问题待解决
		oooooo
		ooABoo
		ooA
		oCA
		*/
		for (size_t i = 0; i < m_borderNodeList.size(); ++i)
		{
			if(m_borderNodeList[i].neighborNodeList.size() <= 1)
			{				
				linkHeadIndexList.push_back((int)i);
			}
		}
	}

	CellLinkNode*	CellSceneBorderLink::getWhiteColorLinkHead(CellScene& cellScene)
	{
		for (size_t i = 0; i < m_borderNodeList.size(); ++i)
		{
			CellLinkNode* node = &m_borderNodeList[i];
			if(node->pos.color == CNC_WHITE)
			{
				if(node->neighborNodeList.size() <= 1)
				{				
					if(cellScene.cellIsBorder(m_borderNodeList[i].pos.x,m_borderNodeList[i].pos.y))
						return node;
				}
			}
		}
		return NULL;
	}

	void    CellSceneBorderLink::getLinkHeadNode(std::vector<int>& linkHeadIndexList,CellScene& cellScene)
	{
		for (size_t i = 0; i < m_borderNodeList.size(); ++i)
		{
			//head定义为只有一个neighbor并且在scene边界的node
			if(m_borderNodeList[i].neighborNodeList.size() <= 1)
			{
				if(cellScene.cellIsBorder(m_borderNodeList[i].pos.x,m_borderNodeList[i].pos.y))
					linkHeadIndexList.push_back((int)i);
			}
		}
	}

	bool    CellSceneBorderLink::isJoined(CellSceneBorderLink& borderLink,CellScene& cellScene)
	{
		std::vector<int> headList;
		getIntersectRegionLinkHeadNode(headList);

		//¼ì²éborderLinkÖÐÊÇ·ñÓÐheadListµÄneighbor node
		for (size_t i = 0; i < headList.size(); ++i)
		{
			CellNode& node1 = m_borderNodeList[headList[i]].pos;
			bool    findNeighbor = false;
			for (size_t j = 0; j < borderLink.m_borderNodeList.size(); ++j)
			{
				if(node1.isNeighbor(borderLink.m_borderNodeList[j].pos))
				{
					findNeighbor = true;
					break;
				}
			}

			if(findNeighbor == false)
				return false;
		}

		return true;
	}

	CellLinkNode*	CellSceneBorderLink::findSingNoBorderNode(CellScene& cellScene)
	{
		for (size_t i = 0; i < m_borderNodeList.size(); ++i)
		{
			CellLinkNode& linkNode = m_borderNodeList[i];

			if(linkNode.pos.color != CNC_SINGLE_NO_BORDER)
			{
				if(linkNode.neighborNodeList.size() == 1)
				{
					if(cellScene.cellIsBorder(linkNode.pos.x,linkNode.pos.y) == false)
						return &linkNode;
				}
			}			
		}
		return NULL;
	}

	void	CellSceneBorderLink::removeSigleNoBorderNode(CellLinkNode* node)
	{
		int neighborCount = 0;
		CellLinkNode* nextNode = NULL;
		for (size_t i = 0; i < node->neighborNodeList.size(); ++i)
		{
			
			CellLinkNode* neighborNode = getLinkNode(node->neighborNodeList[i]);
			if(neighborNode == NULL)
				continue;
			if(neighborNode->pos.color != CNC_SINGLE_NO_BORDER)
				neighborCount++;
			else
				nextNode = neighborNode;
		}

		if(neighborCount <= 1 && nextNode != NULL)
		{
			node->pos.color = CNC_SINGLE_NO_BORDER;
			removeSigleNoBorderNode(nextNode);
		}
	}

	void	CellSceneBorderLink::removeSigleNoBorderNode(CellScene& cellScene)
	{
		CellLinkNode* linkNode = findSingNoBorderNode(cellScene);

		while (linkNode != NULL)
		{
			linkNode->pos.color = CNC_SINGLE_NO_BORDER;
			//其实neighbor只有一个，不用for
			for (size_t i = 0; i < linkNode->neighborNodeList.size(); ++i)
			{
				CellLinkNode* neighborNode = getLinkNode(linkNode->neighborNodeList[i]);
				removeSigleNoBorderNode(linkNode);
			}
			linkNode = findSingNoBorderNode(cellScene);
		}
	}

	CellSceneBorderLink::OrderBorderNodeLink&    CellSceneBorderLink::order(CellLinkNode* headNode,CellScene& cellScene)
	{
		OrderBorderNodeLink orderLink;

		//这里其实可以提到order函数外面，如果有多个orderborder的情况会计算多次，没必要
		removeSigleNoBorderNode(cellScene);

		CellLinkNode* currentNode = headNode;

		while (currentNode)
		{                       
			currentNode->pos.color = CNC_GAY;
			orderLink.push_back(currentNode->listIndex);
			CellLinkNode* tempNode = currentNode;
			currentNode = NULL;
			/*
			      B
				 AC  OO
			 OOOO OOO

			 考虑这种情况，有多个neighbor时优先选择neighbor少的邻居,即从A开始，优先选择B。如果优先选择C，会导致link断裂   ：算法1

			      E
			      D
				  B
			     AC  OO
			 OOOO OOO
			 再考虑上面的情况，按照算法1的情况，会出现A->B->D->E，这样link还是会断裂。要避免这种情况只有去掉非边界的只有一个neighbor的node，注意，这是一个递归过程,先去掉E，再去掉D。
			 这样就简化为算法1能处理的情况。
			*/
			int maxNeighbor = 1000000;
			for (size_t i = 0; i < tempNode->neighborNodeList.size(); ++i)
			{				
				CellLinkNode* nextNode = getLinkNode(tempNode->neighborNodeList[i]);
				if(nextNode->pos.color == CNC_WHITE && nextNode->pos.color != CNC_SINGLE_NO_BORDER)
				{
					const int numOfNeighbor = nextNode->neighborNodeList.size();
					if(numOfNeighbor < maxNeighbor)
					{
						maxNeighbor = numOfNeighbor;
						currentNode = nextNode;                                 
					}
				}
			}       

			//找到另一个端点
			/*if(currentNode == NULL)
				orderNodeList.push_back(tempNode->pos);*/
		}

		m_orderBorderLinkList.push_back(orderLink);
		return m_orderBorderLinkList.back();
	}
}